/*
 * HashMap.h
 *
 *  Created on: May 29, 2010
 *      Author: lucifer
 */

#ifndef	__HASH_MAP_H__
#define	__HASH_MAP_H__

#include <limits.h>

namespace BFX
{

////////////////////////////////////////////////////////////////////////////////


/**
 * Represents a collection of key/value pairs that are organized based on the hash code of the key.
 */
template<class K, class V, class Traits = HashTraits<K> >
class BFX_TMPL HashMap
{
public:
	typedef K KEY;
	typedef const K& ARG_KEY;
	typedef V VALUE;
	typedef const V& ARG_VALUE;

	/**
	 * Used to store a key/value mapping.
	 */
	typedef class Entry
	{
	public:
		K key;
		V value;
	private:
		friend class HashMap<K, V, Traits>;
		int			m_nHashCode;
		Entry*		m_pNext;
		const HashMap*	m_pContainer;
		Entry(int nHashCode, ARG_KEY key, ARG_VALUE value, Entry* pNext, const HashMap* pContainer) :
				key(key), value(value), m_nHashCode(nHashCode), m_pNext(pNext), m_pContainer(pContainer)
		{
		}
	} *POSITION;

	/**
	* The maximum capacity, MUST be a power of two <= 1<<30.
	*/
	static const int MAXIMUM_CAPACITY = (1 << 30);

public:
	/**
	 * Initializes a new instance of the BFX::HashMap with the specified capacity and load factor.
	 * @param nCapacity The initial capacity. MUST be a power of two.
	 * @param fFactor The load factor.
	 */
	HashMap(int nCapacity = 16, float fLoadFactor = 0.75)
	{
		BFX_ASSERT(nCapacity >= 0);
		BFX_ASSERT(fLoadFactor > 0);
		nCapacity = __MIN(nCapacity, MAXIMUM_CAPACITY);

		// find a power of 2 >= nCapacity
		m_nBucketSize = 1;
		while (m_nBucketSize < nCapacity)
			m_nBucketSize <<= 1;

		m_fLoadFactor = fLoadFactor;
		m_nThreshold = (int) __MIN(m_nBucketSize * m_fLoadFactor, MAXIMUM_CAPACITY + 1);
		m_pHashTable = new Entry*[m_nBucketSize];
		memset(m_pHashTable, 0, m_nBucketSize * sizeof(Entry*));

		m_nSize = 0;
	}
	/**
	 * Destroys the instance of BFX::HashMap.
	 */
	virtual ~HashMap()
	{
		Clear();
		delete[] m_pHashTable;
	}

	/**
	 * Gets the number of key/value mappings in this map.
	 * @return The number of key/value mappings in this map.
	 */
	int GetSize() const
	{
		return m_nSize;
	}
	/**
	 * Get a value that indicates whether the map contains no key/value mappings.
	 * @return True if this map is empty; otherwise false.
	 */
	bool IsEmpty() const
	{
		return (m_nSize == 0);
	}

	/**
	 * Determines whether the map contains a specific key.
	 * @param key The key whose presence in this map is to be tested.
	 * @return True if the map contains a mapping for the specified key.; otherwise false.
	 */
	bool Contains(ARG_KEY key) const
	{
		return ContainsKey(key);
	}

	/**
	 * Determines whether the map contains a specific key.
	 * @param key The key whose presence in this map is to be tested.
	 * @return True if the map contains a mapping for the specified key.; otherwise false.
	 */
	bool ContainsKey(ARG_KEY key) const
	{
		return (GetEntry(key) != NULL);
	}

	/**
	 * Determines whether the map contains a specific value.
	 * @param key The value whose presence in this map is to be tested.
	 * @return True if this map contains one or more mapping(s) to the specified value.
	 */
	bool ContainsValue(ARG_VALUE value) const
	{
		for (int i = 0; i < m_nBucketSize; i++)
		{
			for (Entry* p = m_pHashTable[i]; p != NULL; p = p->m_pNext)
			{
				if (value == p->value)
					return true;
			}
		}
		return false;
	}

	/**
	 * Get or sets an value associated with the specified key.
	 * If the argument key value is not found, then it is inserted along with the default value of the data type.
	 * @param key
	 */
	VALUE& operator[](ARG_KEY key)
	{
		Entry* p = GetEntry(key);
		if (p == NULL)
		{
			int nHashCode = Traits::GetHashCode(key);
			int nBucketIndex = (UINT) nHashCode & (m_nBucketSize - 1);
			p = AddEntry(nHashCode, key, VALUE(), nBucketIndex);
		}
		return p->value;
	}

	/**
	 * Sets the value associated with the specified key.
	 * @param key
	 * @param value
	 */
	void Set(ARG_KEY key, ARG_VALUE value)
	{
		int nHashCode = Traits::GetHashCode(key);
		int nBucketIndex = (UINT) nHashCode & (m_nBucketSize - 1);
		for (Entry* p = m_pHashTable[nBucketIndex]; p != NULL; p = p->m_pNext)
		{
			if (p->m_nHashCode == nHashCode && Traits::Equals(p->key, key))
			{
				p->value = value;
				return;
			}
		}

		AddEntry(nHashCode, key, value, nBucketIndex);
	}
	/**
	 * Removes the mapping for the specified key from this map if present.
	 * @param key
	 */
	void Remove(ARG_KEY key)
	{
		int nHashCode = Traits::GetHashCode(key);
		int nBucketIndex = (UINT) nHashCode & (m_nBucketSize - 1);
        Entry* pPrev = m_pHashTable[nBucketIndex];
        Entry* p = pPrev;
        while (p != NULL)
        {
        	Entry* pNext = p->m_pNext;
        	if (p->m_nHashCode == nHashCode && Traits::Equals(p->key, key))
        	{
        		if (pPrev == p)
        			m_pHashTable[nBucketIndex] = pNext;
        		else
        			pPrev->m_pNext = pNext;
        		delete p;
        		m_nSize --;
        	}
        	pPrev = p;
        	p = pNext;
        }
	}

	/**
	 * Removes all of the mappings from this map.
	 */
	void Clear()
	{
		for (int i = 0; i < m_nBucketSize; i++)
		{
			while (m_pHashTable[i] != NULL)
			{
				Entry* p = m_pHashTable[i];
				m_pHashTable[i] = p->m_pNext;
				delete p;
			}
		}
		m_nSize = 0;
	}

	//
	// The following methods uses to compatible with old interfaces.
	//

	bool Lookup(ARG_KEY key, VALUE& rValue) const
	{
		Entry* p = GetEntry(key);
		if (p != NULL)
		{
			rValue = p->value;
			return true;
		}
		return false;
	}

	// Searches the map to find the entry matching the specified key
	// Returns NULL if not found.
	POSITION LookupEntry(ARG_KEY key) const
	{
		return GetEntry(key);
	}
	// Get the first entry object, iterator use only.
	POSITION GetFirstEntry() const
	{
		Entry* p = NULL;
		for (int i = 0; i < m_nBucketSize; i++)
		{
			if ((p = m_pHashTable[i]) != NULL)
				break;
		}
		return p;
	}
	POSITION GetPrevEntry(POSITION pEntry) const
	{
		BFX_ASSERT(pEntry && pEntry->m_pContainer == this);

		Entry* pPrev = NULL;
		int nBucketIndex = (UINT) pEntry->m_nHashCode & (m_nBucketSize - 1);
		for (int i = nBucketIndex; i >= 0; i--)
		{
			pPrev = m_pHashTable[i];
			if (pPrev == NULL || pPrev == pEntry)
				continue;
			for (;;)
			{
				if (pPrev->m_pNext == pEntry || pPrev->m_pNext == NULL)
					break;
				pPrev = pPrev->m_pNext;
			}
			break;
		}

		return pPrev;
	}
	POSITION GetNextEntry(POSITION pEntry) const
	{
		BFX_ASSERT(pEntry && pEntry->m_pContainer == this);

		Entry* pNext = NULL;
		if ((pNext = pEntry->m_pNext) == NULL)
		{
			int nBucketIndex = (UINT) pEntry->m_nHashCode & (m_nBucketSize - 1);
			// go to next bucket
			for (int i = nBucketIndex + 1; i < m_nBucketSize; i++)
				if ((pNext = m_pHashTable[i]) != NULL)
					break;
		}

		return pNext;

	}
	POSITION GetLastEntry() const
	{
		Entry* p = NULL;
		if (m_pHashTable)
		{
			for (int i = (m_nBucketSize - 1); i >= 0; i--)
			{
				for (p = m_pHashTable[i]; ; p = p->m_pNext)
				{
					if (p == NULL || p->m_pNext == NULL)
						break;
				}
				if (p != NULL)
					break;
			}
		}

		return p;
	}
private:
	/*
	 * Returns the entry associated with the specified key in the map.
	 */
	Entry* GetEntry(ARG_KEY key) const
	{
		int nHashCode = Traits::GetHashCode(key);
		int nBucketIndex = (UINT) nHashCode & (m_nBucketSize - 1);
		for (Entry* p = m_pHashTable[nBucketIndex]; p != NULL; p = p->m_pNext)
		{
			if (p->m_nHashCode == nHashCode && Traits::Equals(p->key, key))
				return p;
		}
		return NULL;
	}
	/*
	 * Adds a new entry with the specified key, value and hash code to the specified bucket.
	 */
	Entry* AddEntry(int nHashCode, ARG_KEY key, ARG_VALUE value, int nBucketIndex)
	{
		if (m_nSize >= m_nThreshold && m_pHashTable[nBucketIndex] != NULL)
		{
			Capacity(2 * m_nBucketSize);
			nBucketIndex = nHashCode & (m_nBucketSize - 1);
		}

		Entry* p = m_pHashTable[nBucketIndex];
		m_pHashTable[nBucketIndex] = new Entry(nHashCode, key, value, p, this);
		m_nSize++;
		return m_pHashTable[nBucketIndex];
	}
	/*
	 * Replaces the contents of this map into a new array with a larger capacity.
	 */
	void Capacity(int nCapacity)
	{
		if (m_nBucketSize == MAXIMUM_CAPACITY)
		{
			m_nThreshold = INT_MAX;
			return;
		}

		int nNewBucketSize = nCapacity;
		Entry** pNewTable = new Entry*[nNewBucketSize];
		memset(pNewTable, 0, nNewBucketSize * sizeof(Entry*));

		// transfers all entries from current table to new table.
		for (int i = 0; i < m_nBucketSize; i++)
		{
			Entry* p = m_pHashTable[i];
			while (p != NULL)
			{
				Entry* pNext = p->m_pNext;
				int nBucketIndex = p->m_nHashCode & (nNewBucketSize - 1);
				p->m_pNext = pNewTable[nBucketIndex];
				pNewTable[nBucketIndex] = p;
				p = pNext;
			}
		}

		delete[] m_pHashTable;
		m_pHashTable = pNewTable;
		m_nBucketSize = nNewBucketSize;
		m_nThreshold = (int) __MIN(m_nBucketSize * m_fLoadFactor, MAXIMUM_CAPACITY + 1);
	}

private:
	int		m_nSize;			// The number of key-value mappings contained in this map.
	int		m_nThreshold;		// The next size value at which to resize (capacity * load factor).
	float	m_fLoadFactor;		// The load factor for the hash table.
	int		m_nBucketSize;		// The bucket size of the table. Length MUST Always be a power of two.
	Entry**	m_pHashTable;		// The pointer of the table.
};

}	//	namespace BFX

#endif	//	__HASH_MAP_H__
